/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Lenovo
 * Date: 2025-07-03
 * Time: 22:04
 */
//实现二叉树的基本操作
public class tree {
        public char val;
        public tree left;//左孩子的引用
        public tree right;//右孩子的引用

        public tree() {
        }

        public tree(char val) {
            this.val = val;
        }

        //创建一棵二叉树 返回这棵树的根节点
        public tree createTree() {
          tree a=new tree('A');
          tree b=new tree('B');
          tree c=new tree('C');
          tree d=new tree('D');
          tree e=new tree('E');
          tree f=new tree('F');
          a.left=b;
          a.right=c;
          b.left=d;
          c.left=e;
          c.right=f;
          return a;
        }

        // 前序遍历
        public void preOrder(tree root) {
            if(root==null){
                return ;
            }
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }

        // 中序遍历
        void inOrder(tree root) {
            if(root==null){
                return ;
            }
            inOrder(root.left);
            System.out.print(root.val+" ");
            inOrder(root.right);
        }

        // 后序遍历
        void postOrder(tree root) {
            if(root==null){
                return ;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val+" ");
        }

        //获取树中节点的个数：遍历思路
        public static int nodeSize=0;
        void size(tree root) {
            if(root==null){
                return ;
            }
            nodeSize++;
            size(root.left);
            size(root.right);
        }

        //获取节点的个数：子问题的思路
        int size2(tree root) {
            if(root==null){
                return 0;
            }
            return size2(root.left)+size2(root.right)+1;
        }

        //获取叶子节点的个数：遍历思路
        public static int leafSize = 0;
        void leafNodeSize(tree root) {
            if(root==null){
                return ;
            }
            if(root.left==null&&root.right==null){
                leafSize++;
            }
            leafNodeSize(root.left);
            leafNodeSize(root.right);
        }

        //获取叶子节点的个数：子问题
        int leafNodeSize2(tree root) {
            if(root==null){
                return 0;
            }
            if(root.left==null&&root.right==null){
                return 1;
            }
            return leafNodeSize2(root.left)+leafNodeSize2(root.right);
        }

        //获取第K层节点的个数
        int getKLevelNodeCount(tree root, int k) {
            if(root==null){
                return 0;
            }
            if(k==1){
                return 1;
            }
            return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);
        }

        // 获取二叉树的高度
        // 时间复杂度：O(N)
        int getHeight(tree root) {
            if(root==null){
                return 0;
            }
            int left=getHeight(root.left);
            int right=getHeight(root.right);
            return Math.max(left,right)+1;
        }


        // 检测值为value的元素是否存在
        tree find(tree root, char val) {
            if(root==null) {
                return null;
            }
            if(root.val==val) {
                return root;
            }
            tree left=find(root.left,val);
            if(left!=null){
                return left;
            }
            tree right=find(root.right,val);
            return right;
        }

        //层序遍历
        void levelOrder(tree root) {

        }


        // 判断一棵树是不是完全二叉树
        boolean isCompleteTree(tree root) {
            return true;
        }
}
